package com.zdj;

/**
 * @author zhangdj
 * @date 2021-10-18 11:23:23
 * 二维数组寻找最短路径
 * 从终点开始，递归寻找最短路径
 * 1 4 3
 * 8 7 5
 * 2 1 5
 */
public class MinPath {
    public static void main(String[] args) {
        int[][] arr = new int[][]{{1, 4, 3}, {8, 7, 5}, {2, 1, 5}};
        System.out.println(getMin(arr));
    }

    public static int getMin(int[][] arr) {
        if (arr == null) {
            return 0;
        }
        return getMinPath(arr, arr.length - 1, arr[0].length - 1);
    }

    public static int getMinPath(int[][] arr, int i, int j) {
        if (i == 0 && j == 0) {
            return arr[i][j];
        } else if (i > 0 && j > 0) {
            return arr[i][j] + Math.min(getMinPath(arr, i - 1, j), getMinPath(arr, i, j - 1));
        } else if (i > 0 && j == 0) {
            return arr[i][j] + getMinPath(arr, i - 1, j);
        } else {
            return arr[i][j] + getMinPath(arr, i, j - 1);
        }
    }


}
